package com.leetcode_Onequestion;

/**
 * @Author jsh
 * @Date 2022/4/12 22:48
 * @Version 1.0
 */
/*
* 一个有N个空槽的花园里，每个槽里有一棵花，每天有一棵花会开。给了一个数组flowers，flowers[i] = x表示第i天唯一开花的位置x。
* 又给了一个整数k，判断是否正好有两棵开的花中间有k个空槽，如果有，返回当前天数，否则返回-1。
* 注意：数组是从0开始的，而天数和位置都是从1开始的，所以是第i+1天放的花会在位置x。
* */
public class leetcode_683 {
    public static void main(String[] args) {

        System.out.println(kEmptySlots(new int[]{1, 3, 2}, 1));
    }
    public static int kEmptySlots(int[] flowers,int k){
        int length = flowers.length;
        int[] newflowers = new int[length];
        for (int i = 0; i < length; i++) {
            newflowers[flowers[i]-1] = i+1;
        }
        int left = 0,right=k+1;
        for (int i = 1; right < length; i++) {
            if(newflowers[i] < newflowers[left] || newflowers[i] <=newflowers[right]){
                if(i ==right)
                    return Math.max(newflowers[left],newflowers[right]);

                left = i;
                right = i+k+1;
            }
        }
        return -1;
    }
    public static int kEmptySlots2(int[]  flowers,int k){
        int[]  days = new int[flowers.length];
        for (int i = 0; i < flowers.length; i++) {
            days[flowers[i]-1] = i+1;
        }
        int left=0;  int right =  k+1;
        for (int i = 0; right < flowers.length; i++) {
            if (days[i] <  days[left] || days[i] <= right){
                if (i == right){
                    return Math.max(days[left],days[right]);
                }
                left = i;
                right = i+k+1;
            }
        }
        return -1;
    }
}
